package com.tgy.algorithm.base._递归;

public class _N皇后问题03 {


    public static int queen(int n) {
        if (n <= 3) {
            return 0;
        }

        int[] selects = new int[n];
        return doQueen(selects,0);
    }

    /**
     * selects[i] = n 代表地i行选中第n列 a[i][n]
     * @param selects
     * @param index
     * @return
     */
    public static int doQueen(int[] selects,int index) {

        int len = selects.length;
        if (index >= len) {
            // 到达底部，是一种选择
            return 1;
        }

        int ret = 0;
        for (int i = 0; i < len; i++) {
            // 举例从第0列到len-1列, a[index][i]
            selects[index] = i;
            if (isValid(selects,index)) {
                ret += doQueen(selects,index+1);
            }
        }

        return ret;
    }

    public static boolean isValid(int[] selects,int index) {

        // [index][selects[index]]
        for (int i = 0; i < index; i++) {
            // [i][select[i]]
            if ((selects[index] == selects[i]) ||
                    (Math.abs(index - i) == (Math.abs(selects[index] - selects[i])))) {
                return false;
            }
        }
        return true;
    }

    public static void printBit(long n,int bit) {

        for (int i = bit - 1; i >=0; i--) {
            String bitStr = (n & (1 << i)) == 0 ? "0":"1";
            System.out.print(bitStr);
        }
        System.out.println();
    }

    public static int getLastRightZero(int n) {
        // 1010
        // 0101
        // 0110
        return n & (~n + 1);
    }

    public static int getOneNum(int n) {

        int all = 0;

        while (n != 0) {
            int lastRight = getLastRightZero(n);
            all++;
            n = n ^ lastRight;
        }

        return all;
    }

    public static void main(String[] args) {
//        int queen = queen(8);
//        System.out.println(queen);
//        getLastRightZero(100)
        int rightZero = getLastRightZero(100);
        printBit(100,Integer.SIZE);
        printBit(rightZero,Integer.SIZE);
        System.out.println(getOneNum(100));
    }
}
